#include "status.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node{
	datatype data;
	struct node *lchild;
	struct node *rchild;
}bitree;


void init(bitree **root){
	bitree *node=(bitree*)malloc(sizeof(bitree));
	if(!node)exit(overflow);
	node->lchild=NULL;
	node->rchild=NULL;
	*root=node;
}
bitree* leftinsert(bitree *cur,datatype x){
	bitree *s,*p;
	if(cur==NULL) return NULL;
	p=cur->lchild;
	s=(bitree*)malloc(sizeof(bitree));
	s->data=x;
	s->lchild=p;
	s->rchild=NULL;
	cur->lchild=s;
	return s;
}
bitree* rightinsert(bitree *cur,datatype x){
	bitree *s,*p;
	if(cur==NULL) return NULL;
	p=cur->rchild;
	s=(bitree*)malloc(sizeof(bitree));
	s->data=x;
	s->lchild=NULL;
	s->rchild=p;
	cur->rchild=s;
	return s;
}
void destroy(bitree **root){
	if(*root!=NULL && (*root)->lchild!=NULL)
		destroy(&(*root)->lchild);
	if(*root!=NULL && (*root)->rchild!=NULL)
		destroy(&(*root)->rchild);
	free(*root);
}
bitree* dellchild(bitree *cur){
	if(cur==NULL||cur->lchild==NULL) return NULL;
	destroy(&cur->lchild);
	cur->lchild=NULL;
	return cur;
}
bitree* delrchild(bitree *cur){
	if(cur==NULL||cur->rchild==NULL) return NULL;
	destroy(&cur->rchild);
	cur->rchild=NULL;
	return cur;
}
void printdata(datatype x){
	printf("%c ",x);
}
void preorder(bitree *root,void visit(datatype item)){
	if(root==NULL) return;
	visit(root->data);
	preorder(root->lchild,visit);
	preorder(root->rchild,visit);
}
void inorder(bitree *root,void visit(datatype item)){
	if(root==NULL) return;
	inorder(root->lchild,visit);
	visit(root->data);
	inorder(root->rchild,visit);
}
void postorder(bitree *root,void visit(datatype item)){
	if(root==NULL) return;
	postorder(root->lchild,visit);
	postorder(root->rchild,visit);
	visit(root->data);
}
void printtree(bitree *root,int n){
	int i;
	if(root==NULL)return;
	printtree(root->rchild,n+1);
	for(i=0;i<n-1;i++)printf("     ");
	if(n>0){
		printf("---");
		printf("%c\n",root->data);
	}
	printtree(root->lchild,n+1);
}
bitree *search(bitree *root,datatype x){
	bitree *find=NULL;
	if(root!=NULL){
		if(root->data==x){
			find=root;
		}else{
			find=search(root->lchild,x);
			if(find==NULL){
				find=search(root->rchild,x);
			}
		}
	}
	return find;
}
int main(){
	bitree *root,*p;
	init(&root);
	p=leftinsert(root,'A');
	p=leftinsert(p,'B');
	p=leftinsert(p,'D');
	p=rightinsert(p,'G');
	p=rightinsert(root->lchild,'C');
	leftinsert(p,'E');
	rightinsert(p,'F');
	preorder(root,printdata);
	printf("\n");
	inorder(root,printdata);
	printf("\n");
	postorder(root,printdata);
	printf("\n");
	printtree(root,0);
	datatype item='E';
	bitree *find=search(root,item);
	if(find!=NULL)printf("%c find\n",item);
	else printf("%c not found\n",item);
	item='Z';
	find=search(root,item);
	if(find!=NULL)printf("%c find\n",item);
	else printf("%c not found\n",item);
	dellchild(root);
	delrchild(root);
	destroy(&root);
}
